package org.example;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Test2 {
    //leetcode 406 根据身高重建队列 https://leetcode.cn/problems/queue-reconstruction-by-height/description/

    /**
     * 这个题目因为是二维的数组，如果两个维度同时贪心的话，就不行，所以就需要先确定一个维度，如果先确定people[n][1]的话
     * 如果按照people[n][1]升序排列，此时是不满足最终结果的，所以就还需要身高进行调整，如果调整，那么people[n][1]就不符合了
     * 所以我们选择先固定people[0][n]，按照people[0][n]降序排列，这样就可以保证people[n]，第n和人之前的人都是高于第n个人的
     * 调整people[n][1]的话，就只需要将people[n]第n个人插入到people[1]位置上，这样就保证该人之前只有people[1]个比他高的人
     * @param people
     * @return
     */
    public int[][] reconstructQueue(int[][] people) {
        //将数组根据身高从高到矮排序，如果身高相同就按照k升序排列
        //
        Arrays.sort(people,(a, b) -> {
            if (a[0] == b[0]) return a[1] - b[1];
            return b[0] - a[0];
        });
        //将数组进行排序之后，那么i位置之前的身高都比i高，那么people最终的位置就是people[1]的值
        List<int[]> ret = new LinkedList<>();
        for (int[] n : people) {
            ret.add(n[1],n);
        }
        //toArray()方法默认返回的类型是Object[]，这里要求返回的类型是int[][]
        //那么就需要用到toArray()方法的另一个重载方法 <T> T[] toArray(T[] a);
        return ret.toArray(new int[people.length][]);
    }
}
